package dynamicprogramming


// 从左上角到右下角
// 向下或向左走
// 有障碍物
func uniquePaths(obstacleGrid [][]int) int {
	m,n := len(obstacleGrid),len(obstacleGrid[0])
	if m==0 || n==0{
		return 0
	}
	if obstacleGrid[0][0] == 1{
		return 0
	}
	dp := make([][]int,m)
	for i:=range dp{
		dp[i] = make([]int, n)
	}
	// 初始化
	// 初始化, 如果是障碍物, 后面的就都是0, 不用循环了
	for i := 0; i < m && obstacleGrid[i][0] == 0; i++ {
		dp[i][0] = 1
	}
	for i := 0; i < n && obstacleGrid[0][i] == 0; i++ {
		dp[0][i] = 1
	}
	for i:=1;i<m;i++{
		for j:=1;j<n;j++{
			if obstacleGrid[i][j]==1{
				continue
			}
			if (obstacleGrid[i][j] == 0) { // 当(i, j)没有障碍的时候，再推导dp[i][j]
				dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
			}
		}
	}
	return dp[m-1][n-1]
}


// 其次，可以尝试dfs